package leetcode.editor.cn;

//给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 13
//输出：6
// 
//
// 示例 2： 
//
// 
//输入：n = 0
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 10⁹ 
// 
// Related Topics 递归 数学 动态规划 👍 390 👎 0

//Java：数字 1 的个数
public class NumberOfDigitOne_233{
    public static void main(String[] args) {
        Solution solution = new NumberOfDigitOne_233().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countDigitOne(int n) {
        char[] chars = String.valueOf(n).toCharArray();
        int len = chars.length, count =0;
        for (int i = 0; i < len; i++) {
            if (chars[len-i-1]!='1'){
                int num1=0;
                for (int j = 0; j < len-i-1; j++) { // 前面的数字
                    num1= num1*10+chars[j]-'0';
                }
                if(chars[len-i-1]!='0') num1+=1;
                count+=num1*Math.pow(10,i);
//                System.out.println(count);
            }
            if(chars[len-i-1]=='1'){
                int num1=0,num2=0;
                for (int j = 0; j < len-i-1; j++) { // 前面的数字
                    num1= num1*10+chars[j]-'0';
                }
                for (int j = len-i; j < len; j++) { // 后面的数字
                    num2=num2*10+chars[j]-'0';
                }
                count+=num1*Math.pow(10,i)+num2+1;
//                System.out.println(count);
            }
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
